package com.tgy.algorithm.base._排序;

import java.util.Arrays;

public class _快速排序 {

    public static void quickSort(int[] nums) {
        doQuickSort(nums, 0, nums.length - 1);
    }

    public static void doQuickSort(int[] nums,int left,int right) {
        if (left >= right) {
            return;
        }

        int[] partition = partition(nums, left, right);
        doQuickSort(nums,left,partition[0]);
        doQuickSort(nums,partition[1],right);
    }


    public static int[] partition(int[] nums,int left,int right) {

        // leftIndex始终是小于povit的index
        int leftIndex = left - 1;
        // rightIndex 的下一个是大于povit的值
        int rightIndex = right - 1;
        int index = left;
        int povit = nums[right];
        while (index <= rightIndex) {
            int value = nums[index];
            if (value < povit) {
                // leftIndex 存放小于povit的值
                if (leftIndex+1 != index) {
                    swap(nums,leftIndex+1,index);
                }
                leftIndex++;
                index++;
            }else if (value == povit) {
                index++;
            }else {
                // 交换大于povit的值,只对 rightIndex--,index不动，因为要对rightIndex的值进行比较
                swap(nums,index,rightIndex--);
            }
        }

        swap(nums,rightIndex+1, right);
        return new int[]{leftIndex,rightIndex+2};
    }

    public static void swap(int[] nums,int i,int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {3,2,4,1,5,7,6};
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
